/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class MaximumAverageSubarrayII {
    public static double findMaxAverage(int[] nums, int k) {
//        double maxAvg=0;
//        double sum=0;
//        int lastK=k;
//        for (int i = 0; i < k; i++) {
//			sum+=nums[i];
//		}
//        maxAvg=sum/k;
//        for (int i = k; i < nums.length; i++) {
//			sum=maxAvg*lastK+nums[i];
//			double avg=sum/(lastK+1);
//			int maxK=0;
//			if(avg>maxAvg){
//				maxAvg=avg;
//				maxK=lastK+1;
//			}
//			for (int x = 1; x < lastK-k; x++) {
//				sum-=nums[i-x];
//				avg=sum/(lastK-x+1);
//				if(avg>maxAvg){
//					maxAvg=avg;
//					maxK=lastK-x+1;
//				}
//			}
//			lastK=maxK;
//		}
    	double maxAvg=-1*Double.MAX_VALUE;
    	int n=nums.length;
    	double[] sum=new double[n];
    	for (int i = 0; i < sum.length; i++) {
			sum[i]=(i==0?0:sum[i-1])+nums[i];
		}
    	
    	for (int i = k-1; i < n; i++) {
    		double cur=sum[i]/(i+1);
    		for (int j = 0; j <= i-k; j++) {
    			double s=sum[i]-sum[j];
				cur=Math.max(cur, s/(i-j));
			}
    		maxAvg=Math.max(cur, maxAvg);
		}
    	
        return maxAvg;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] nums={-1};
		int k=1;
		System.out.println(findMaxAverage(nums, k));
	}

}
